Dù thi đấu rất thành công tại câu lạc bộ, nhưng chưa bao giờ Deco được gọi vào đội tuyển Brasil. Anh đã đề cập vài lần về khả năng anh chơi cho Bồ Đào Nha. Vào năm 2002, sau sáu năm sống và thi đấu tại Bồ Đào Nha, anh đã được nhập quốc tịch. Vài ngày sau sự kiện này, Luiz Felipe Scolari, một người Brasil đang dẫn dắt tuyển Bồ Đào Nha cho gọi Deco vào đội tuyển. Việc làm của Scolari đã gây ra nhiều phản đối, song cũng nhận được sự ủng hộ từ phía FC Porto. Cuối cùng, sau nhiều tranh luận sôi nổi, Deco cũng được thi đấu trận đầu tiên trong màu áo Bồ Đào Nha; trùng hợp thay đó lại là trận đấu với đội bóng quê hương mình, diễn ra trên sân Estádio das Antas ngày 29 tháng 3 năm 2003. Anh chỉ chơi 9 phút trong trận đó, nhưng đủ để ghi một bàn vào lưới Brasil từ quả phạt trực tiếp, giúp Bồ Đào Nha thắng 2-1. Đó cũng là lần đầu tiên Bồ Đào Nha thắng Brasil kể từ World Cup 1966 ở Anh. Sau trận đấu này, anh trở thành nhân vật thường xuyên trong đội tuyển quốc gia, tuy vẫn chịu sự kỳ thị từ phía Luís Figo, người mà rất lâu sau cũng chưa chịu chấp nhận giá trị của một cầu thủ ngoại quốc xin nhập quốc tịch, và thường gọi đó là thủ đoạn "lợi dụng"[6]. Bất chấp mọi bình phẩm, Deco dần tỏa sáng trong đội hình tuyển quốc gia Bồ Đào Nha và đến hôm nay đã trở thành nhân vật chủ chốt của đội. Anh đã ghi 4 bàn sau 55 lần thi đấu cho đội, tính đến tháng 6 năm 2008.

World Cup 2006

Tại kỳ World Cup 2006, anh ghi bàn thắng đầu tiên cho Bồ Đào Nha ở trận thứ 2 bảng D với Iran. Bàn thắng ghi ở phút thứ 63 trước khi Cristiano Ronaldo ấn định chiến thắng 17 phút sau đó. Ở trận đầu tiên của vòng đấu loại trực tiếp, anh nhận thẻ vàng thứ 2 khi gặp Hà Lan, thẻ đầu tiên là do 1 pha chuồi bóng với Johnny Heitinga, nó đã khiến anh không thể có mặt ở trận tứ kết với Anh. Bồ Đào Nha dừng chân ở vị trí thứ 4 và trở thành một hiện tượng của giải.

Euro 2008

Vào ngày 11 tháng 6, Deco ghi bàn mở màn trong trận đấu thứ hai của đội tuyển tại vòng chung kết Euro 2008 với Cộng hòa Séc. Trận đấu kết thúc với tỉ số 3 - 1, Deco góp công đưa tuyển vào vòng tứ kết gặp Đức. Ở trận tứ kết, dù Deco được đánh giá là chơi tốt nhất bên phía Bồ Đào Nha, đội bóng của anh vẫn phải ngậm ngùi chia tay giải đấu khi để thua 2-3.

Bàn thắng quốc tế